//给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。 
//
// 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。 
//
// 
//
// 例如，给定三角形： 
//
// [
//     [2],
//    [3,4],
//   [6,5,7],
//  [4,1,8,3]
//]
// 
//
// 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。 
//
// 
//
// 说明： 
//
// 如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。 
// Related Topics 数组 动态规划 
// 👍 582 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：三角形最小路径和
public class P120Triangle {

    /**
     *
     * 思路：动态规划，类似机器人走方格，只能走右或走下 走到最后面。
     *      dp[m][n]到达m,n 的最短路径, 就是比较上一层的上方和左上方哪个最小，然后加本格的数值。
     *      最后比较最后一行哪个最小就是结果了。
     *
     * 执行用时： 3 ms , 在所有 Java 提交中击败了 73.80% 的用户 内存消耗： 39.9 MB , 在所有 Java 提交中击败了 56.22% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            int n = triangle.size();        // n 层
            if (n == 0) {
                return 0;
            }
            // dp[m][n] 表示到达m,n 这个点，的最短路径
            int[][] dp = new int[n][n];
            dp[0][0] = triangle.get(0).get(0);

            for (int i = 1; i < n; i++) {
                List<Integer> temp = triangle.get(i);
                for (int k = 0; k < temp.size(); k++) {
                    if (k == 0) {
                        // 头
                        dp[i][k] = dp[i - 1][k] + temp.get(k);
                    } else if (k == temp.size() - 1) {
                        // 尾
                        dp[i][k] = dp[i - 1][k - 1] + temp.get(k);
                    } else {
                        if (dp[i - 1][k] <= dp[i - 1][k - 1]) {
                            dp[i][k] = dp[i - 1][k] + temp.get(k);
                        } else {
                            dp[i][k] = dp[i - 1][k - 1] + temp.get(k);
                        }
                    }
                }
            }

            Integer min = null;
            int[] temp  = dp[n - 1];
            for (Integer a : temp) {
                if (min == null) {
                    min = a;
                } else {
                    if (a.compareTo(min) < 0) {
                        min = a;
                    }
                }
            }
            return min == null ? 0 : min;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        List<List<Integer>> list = new ArrayList<>();
        List<Integer> a1 = new ArrayList<>();
        a1.add(2);
        List<Integer> a2 = new ArrayList<>();
        a2.add(3);
        a2.add(4);
        List<Integer> a3 = new ArrayList<>();
        a3.add(6);
        a3.add(5);
        a3.add(7);
        List<Integer> a4 = new ArrayList<>();
        a4.add(4);
        a4.add(1);
        a4.add(8);
        a4.add(3);

        list.add(a1);
        list.add(a2);
        list.add(a3);
        list.add(a4);


        Solution solution = new P120Triangle().new Solution();
        System.out.println(solution.minimumTotal(list));
        // TO TEST
    }

}